// 给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。

// 进阶：

// 你可以在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序吗？

// 来源：力扣（LeetCode）
// 链接：https://leetcode-cn.com/problems/sort-list
// 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

#include<bits/stdc++.h>
#include<string>
#include<vector>
#include<unordered_set>
#include<set>
#include<queue>
using namespace std;

// 非标准解法，空间复杂度n，时间复杂度依据排序算法2，估计是nlogn

// 执行用时：
// 84 ms
// , 在所有 C++ 提交中击败了
// 92.23%
// 的用户
// 内存消耗：
// 29.4 MB
// , 在所有 C++ 提交中击败了
// 73.78%
// 的用户

 struct ListNode {
     int val;
     ListNode *next;
     ListNode() : val(0), next(nullptr) {}
     ListNode(int x) : val(x), next(nullptr) {}
     ListNode(int x, ListNode *next) : val(x), next(next) {}
 };


class Solution {
public:
    ListNode* sortList(ListNode* head) {
        vector<int> value;
        ListNode* p =head;
        int pos =0;
        while(p!=NULL){
            value.push_back(p->val);
            p = p->next;
        }
        sort(value.begin(),value.end());
        p = head;
        pos = 0;
        while(p!=NULL){
            p->val = value[pos];
            pos++;
            p = p->next;
        }
        return head;
    }
};